{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #As Far from Land as Possible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #地图分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你现在手里有一份大小为<meta charset=\"UTF-8\" />&nbsp;<code>n x n</code>&nbsp;的 网格 <code>grid</code>，上面的每个 单元格 都用&nbsp;<code>0</code>&nbsp;和&nbsp;<code>1</code>&nbsp;标记好了。其中&nbsp;<code>0</code>&nbsp;代表海洋，<code>1</code>&nbsp;代表陆地。</p>\n",
    "\n",
    "<p>请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>我们这里说的距离是「曼哈顿距离」（&nbsp;Manhattan Distance）：<code>(x0, y0)</code> 和&nbsp;<code>(x1, y1)</code>&nbsp;这两个单元格之间的距离是&nbsp;<code>|x0 - x1| + |y0 - y1|</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/08/17/1336_ex1.jpeg\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,1],[0,0,0],[1,0,1]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释： </strong>\n",
    "海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/08/17/1336_ex2.jpeg\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,0],[0,0,0],[0,0,0]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释： </strong>\n",
    "海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [as-far-from-land-as-possible](https://leetcode.cn/problems/as-far-from-land-as-possible/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [as-far-from-land-as-possible](https://leetcode.cn/problems/as-far-from-land-as-possible/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,1],[0,0,0],[1,0,1]]', '[[1,0,0],[0,0,0],[0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 多次遍历，每次沿着海岸线向内延伸，直到没有0，获取当前遍历次数\n",
    "        n = len(grid)\n",
    "        cnt = 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            cnt += 1\n",
    "            flag = False\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == cnt:\n",
    "                        for i2, j2 in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                            if -1<i2<n and -1<j2<n and grid[i2][j2] == 0:\n",
    "                                flag = True\n",
    "                                grid[i2][j2] = cnt + 1\n",
    "            \n",
    "        return cnt - 1 or -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = 0 if grid[i][j] == 1 else 1000\n",
    "\n",
    "        # res = -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    continue\n",
    "\n",
    "                if i - 1 >= 0:\n",
    "                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j])\n",
    "                if j - 1 >= 0:\n",
    "                    dp[i][j] = min(dp[i][j - 1] + 1, dp[i][j])\n",
    "                # res = max(res, dp[i][j])\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j]:\n",
    "                    continue\n",
    "\n",
    "                if i + 1 < m:\n",
    "                    dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j])\n",
    "                if j + 1 < n:\n",
    "                    dp[i][j] = min(dp[i][j + 1] + 1, dp[i][j])\n",
    "\n",
    "                # res = max(res, dp[i][j])\n",
    "        # print(dp)\n",
    "        res = -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    continue\n",
    "                res = max(res, dp[i][j])\n",
    "        if res == 1000:\n",
    "            return -1\n",
    "        return res\n",
    "\n",
    "\n",
    "# bfs\n",
    "# class Solution:\n",
    "#     def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "#         queue = []\n",
    "#         m, n = len(grid), len(grid[0])\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if grid[i][j] == 1:\n",
    "#                     queue.append((i, j))\n",
    "#                 else:\n",
    "#                     grid[i][j] = -1\n",
    "#         res = 0\n",
    "#         pos = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "#         while queue:\n",
    "#             i, j = queue.pop(0)\n",
    "#             for x, y in pos:\n",
    "#                 pI, pJ = i + x, j + y\n",
    "#                 if pI >= 0 and pI < m and pJ >= 0 and pJ < n and grid[pI][pJ] == -1:\n",
    "#                     grid[pI][pJ] = grid[i][j] + 1\n",
    "#                     res = max(res, grid[pI][pJ])\n",
    "#                     queue.append((pI, pJ))\n",
    "#         # print(grid)\n",
    "#         return res - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 多次遍历，每次沿着海岸线向内延伸，直到没有0，获取当前遍历次数\n",
    "        n = len(grid)\n",
    "        cnt = 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            cnt += 1\n",
    "            flag = False\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == cnt:\n",
    "                        for i2, j2 in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                            if -1<i2<n and -1<j2<n and grid[i2][j2] == 0:\n",
    "                                flag = True\n",
    "                                grid[i2][j2] = cnt + 1\n",
    "            \n",
    "        return cnt - 1 or -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dp1 = [float('inf')] * n\n",
    "        dp2 = [float('inf')] * n\n",
    "        d1 = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dp1[j] = 0\n",
    "                else:\n",
    "                    if j == 0:\n",
    "                        dp1[j] += 1\n",
    "                    else:\n",
    "                        dp1[j] = 1 + min(dp1[j], dp1[j-1])\n",
    "            for k in range(n-1, -1, -1):\n",
    "                if grid[i][k] == 1:\n",
    "                    dp2[k] = 0\n",
    "                else:\n",
    "                    if k == n-1:\n",
    "                        dp2[k] += 1\n",
    "                    else:\n",
    "                        dp2[k] = 1 + min(dp2[k], dp2[k+1])\n",
    "                d1[i][k] = min(dp1[k], dp2[k])\n",
    "        dp1[-1] = float('inf')\n",
    "        dp2[0] = float('inf')\n",
    "        res = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    dp1[j] = 0\n",
    "                else:\n",
    "                    if j == n-1:\n",
    "                        dp1[j] += 1\n",
    "                    else:\n",
    "                        dp1[j] = 1 + min(dp1[j], dp1[j+1])\n",
    "            for k in range(n):\n",
    "                if grid[i][k] == 1:\n",
    "                    dp2[k] = 0\n",
    "                else:\n",
    "                    if k == 0:\n",
    "                        dp2[k] += 1\n",
    "                    else:\n",
    "                        dp2[k] = 1 + min(dp2[k], dp2[k-1])\n",
    "                if res < min(d1[i][k], dp1[k], dp2[k]) < 2*n:\n",
    "                    res = min(d1[i][k], dp1[k], dp2[k])\n",
    "        if res <= 0 or res > 2*n:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "def gen_it(cur, n):\n",
    "    i, j = cur\n",
    "    if i - 1 >= 0:\n",
    "        yield i - 1, j\n",
    "    if i + 1 < n:\n",
    "        yield i + 1, j\n",
    "    if j - 1 >= 0:\n",
    "        yield i, j - 1\n",
    "    if j + 1 < n:\n",
    "        yield i, j + 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = deque([])\n",
    "        touched = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append((i, j))\n",
    "                    touched.add((i, j))\n",
    "        if len(q) == n*n or len(q) == 0:\n",
    "            return -1\n",
    "        step = -1\n",
    "        while q:\n",
    "            q_size = len(q)\n",
    "            for _ in range(q_size):\n",
    "                cur = q.popleft()\n",
    "                for next_pos in gen_it(cur, n):\n",
    "                    if next_pos not in touched:\n",
    "                        touched.add(next_pos)\n",
    "                        q.append(next_pos)\n",
    "            step += 1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        queue = collections.deque()\n",
    "        visited = set()\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j))\n",
    "        \n",
    "        if not queue or len(queue) == n ** 2:\n",
    "            return -1\n",
    "        \n",
    "        step = -1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                y, x = queue.popleft()\n",
    "                for newy, newx in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:\n",
    "                    if 0 <= newy < n and 0 <= newx < n and grid[newy][newx] == 0 and (newy, newx) not in visited:\n",
    "                        queue.append((newy, newx))\n",
    "                        visited.add((newy, newx))\n",
    "            step += 1\n",
    "        \n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        temp=[[float('inf')]*(n+2) for _ in range(n+2)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if grid[i-1][j-1]==1:\n",
    "                    temp[i][j]=0\n",
    "                else:\n",
    "                    temp[i][j]=min(temp[i-1][j]+1,temp[i][j-1]+1)\n",
    "        ans=-float('inf')\n",
    "        for i in range(n,0,-1):\n",
    "            for j in range(n,0,-1):\n",
    "                temp[i][j]=min(temp[i][j], temp[i+1][j]+1,temp[i][j+1]+1)\n",
    "                ans=max(ans, temp[i][j])\n",
    "        return ans if ans!=float('inf') and ans!=0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        hasLand = False\n",
    "        hasOcean = False\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    hasLand = True\n",
    "                else:\n",
    "                    hasOcean = True\n",
    "\n",
    "        if not hasLand or not hasOcean:\n",
    "            return -1\n",
    "        \n",
    "        dp = [[float(\"inf\")] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    if i > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)\n",
    "                    if j > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 0:\n",
    "                    if i < n - 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1)\n",
    "                    if j < n - 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1)\n",
    "        \n",
    "        res = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    res = max(res, dp[i][j])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        q=deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] ==1:\n",
    "                    q.append((i,j))\n",
    "        sz = len(q)\n",
    "        if sz==n*n or sz ==0 :\n",
    "            return -1\n",
    "        \n",
    "        while q:\n",
    "            \n",
    "            x,y =q.popleft()\n",
    "            for nx,ny in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny] ==0:\n",
    "                    grid[nx][ny] =grid[x][y]+1\n",
    "                    q.append((nx,ny))\n",
    "\n",
    "        return grid[x][y]-1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        que = deque()\n",
    "        n = len(grid)\n",
    "        step = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    que.append((i,j))\n",
    "        if len(que) == 0 or len(que) == n*n:\n",
    "            return step\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                x, y = que.popleft()\n",
    "                for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:\n",
    "                        que.append((xi, yj))\n",
    "                        grid[xi][yj] = -1\n",
    "            step += 1\n",
    "        return step\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        one_list = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                if grid[i][j] == 1:\n",
    "                    one_list.append((i,j))\n",
    "\n",
    "\n",
    "        if len(one_list) == 0 or len(one_list) == len(grid)**2:\n",
    "            return -1\n",
    "        \n",
    "        step = -1\n",
    "        while one_list:\n",
    "            for _ in range(len(one_list)):\n",
    "                i,j = one_list.pop(0)\n",
    "\n",
    "                for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    if len(grid) > ni >=0 and len(grid) > nj >=0:\n",
    "                        if grid[ni][nj] == 0:\n",
    "                            grid[ni][nj] = -1\n",
    "                            one_list.append((ni,nj))\n",
    "            step += 1\n",
    "        return step\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        result, n = -1, len(grid)\n",
    "        q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                for i1, j1 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                    if 0 <= i1 < n and 0 <= j1 < n and not grid[i1][j1]:\n",
    "                        grid[i1][j1] = 1\n",
    "                        q.append((i1, j1))\n",
    "            result += 1\n",
    "        return result or -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return []\n",
    "        n = len(grid)\n",
    "        dp = [[float(\"inf\")]*n for _ in range(n)]\n",
    "        land = False\n",
    "        sea = False\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                    land = True\n",
    "                else:\n",
    "                    sea = True\n",
    "        if not land or not sea:\n",
    "            return -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    if i >= 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][j]+1)\n",
    "                    if j >= 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j-1]+1)\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 0:\n",
    "                    if i <= n-2:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i+1][j]+1)\n",
    "                    if j <= n-2:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j+1]+1)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        queue = deque()\n",
    "\n",
    "        # 将所有陆地单元格的坐标加入队列\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j))\n",
    "\n",
    "        if len(queue) == 0 or len(queue) == n * n:\n",
    "            return -1\n",
    "\n",
    "        distance = -1\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                x, y = queue.popleft()\n",
    "\n",
    "                # 将相邻的海洋单元格加入队列，并将它们的距离更新为当前单元格距离+1\n",
    "                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    new_x = x + dx\n",
    "                    new_y = y + dy\n",
    "                    if new_x >= 0 and new_x < n and new_y >= 0 and new_y < n and grid[new_x][new_y] == 0:\n",
    "                        grid[new_x][new_y] = 2\n",
    "                        queue.append((new_x, new_y))\n",
    "\n",
    "            distance += 1\n",
    "\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        # grid = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]\n",
    "        # row = len(grid)\n",
    "        # col = len(grid[0])\n",
    "\n",
    "        # ocean = []\n",
    "        # land = []\n",
    "        # for i in range(row):\n",
    "        #     for j in range(col):\n",
    "        #         if grid[i][j] == 0:\n",
    "        #             ocean.append((i,j))\n",
    "        #         else:\n",
    "        #             land.append((i,j))\n",
    "        # print(ocean)\n",
    "        # print(land)\n",
    "\n",
    "        # max_distance = -1\n",
    "\n",
    "        # for x, y in ocean:\n",
    "        #     tmp = []\n",
    "        #     for dx, dy in land:\n",
    "        #         tmp.append(abs(x-dx) + abs(y-dy))\n",
    "        #     # print(min(tmp))\n",
    "        #     if tmp and min(tmp) > max_distance:\n",
    "        #         max_distance = min(tmp)\n",
    "        # print(max_distance)\n",
    "        # return max_distance\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not grid or len(grid[0]) == 0:\n",
    "        #     return -1\n",
    "\n",
    "        # n = len(grid)\n",
    "        # lands = []\n",
    "\n",
    "        # # 遍历整个网格，将所有陆地的位置记录下来\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j] == 1:\n",
    "        #             lands.append((i, j))\n",
    "\n",
    "        # # 如果整个网格上只有陆地或只有海洋，返回-1\n",
    "        # if len(lands) == 0 or len(lands) == n * n:\n",
    "        #     return -1\n",
    "\n",
    "        # max_distance = -1\n",
    "\n",
    "        # # 计算海洋到陆地的最远距离\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j] == 0:\n",
    "        #             distance = min([abs(x - i) + abs(y - j) for (x, y) in lands])\n",
    "        #             max_distance = max(max_distance, distance)\n",
    "\n",
    "        # return max_distance\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not grid or len(grid[0]) == 0:\n",
    "        #     return -1\n",
    "\n",
    "        # n = len(grid)\n",
    "        # q = deque()\n",
    "        # max_distance = -1\n",
    "\n",
    "        # # 遍历整个网格，将所有陆地的位置放入队列中\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j] == 1:\n",
    "        #             q.append((i, j))\n",
    "\n",
    "        # # 如果整个网格上只有陆地或只有海洋，返回-1\n",
    "        # if len(q) == 0 or len(q) == n * n:\n",
    "        #     return -1\n",
    "\n",
    "        # # 网格的上、下、左、右四个方向\n",
    "        # directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        # # BFS\n",
    "        # while q:\n",
    "        #     size = len(q)\n",
    "        #     # 每次处理一层\n",
    "        #     for i in range(size):\n",
    "        #         x, y = q.popleft()\n",
    "        #         # 遍历四个方向\n",
    "        #         for dx, dy in directions:\n",
    "        #             nx, ny = x + dx, y + dy\n",
    "        #             if nx >= 0 and nx < n and ny >= 0 and ny < n and grid[nx][ny] == 0:\n",
    "        #                 q.append((nx, ny))\n",
    "        #                 grid[nx][ny] = grid[x][y] + 1\n",
    "        #                 max_distance = max(max_distance, grid[nx][ny] - 1)\n",
    "\n",
    "        # return max_distance\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # row = len(grid)\n",
    "        # col = len(grid[0])\n",
    "        \n",
    "        # land = []\n",
    "        # for i in range(row):\n",
    "        #     for j in range(col):\n",
    "        #         if grid[i][j] == 1:\n",
    "        #             land.append((i, j))\n",
    "        \n",
    "        # max_distance = -1\n",
    "        # directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        \n",
    "        # while land:\n",
    "        #     for _ in range(len(land)):\n",
    "        #         x, y = land.pop(0)\n",
    "        #         for dx, dy in directions:\n",
    "        #             nx = x + dx\n",
    "        #             ny = y + dy\n",
    "        #             if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == 0:\n",
    "        #                 grid[nx][ny] = grid[x][y] + 1\n",
    "        #                 land.append((nx, ny))\n",
    "        #                 max_distance = max(max_distance , grid[nx][ny] - 1)\n",
    "        # return max_distance\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        q = deque()\n",
    "        \n",
    "        land = []\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    # land.append((i, j))\n",
    "                    q.append((i, j))\n",
    "        \n",
    "        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        max_distance = -1\n",
    "        \n",
    "        # while land:\n",
    "        while q:\n",
    "            # for _ in range(len(land)):\n",
    "                # x, y = land.pop(0)\n",
    "            for _ in range(len(q)):\n",
    "                x, y = q.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    nx = x + dx\n",
    "                    ny = y + dy\n",
    "                    if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == 0:\n",
    "                        grid[nx][ny] = grid[x][y] + 1\n",
    "                        # land.append((nx, ny))\n",
    "                        q.append((nx, ny))\n",
    "                        max_distance = max(max_distance , grid[nx][ny] - 1)\n",
    "        return max_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        ocean = 0\n",
    "        #queue = deque([(i,j) for i in range(n) for j in range(n) if grid[i][j] ==1])\n",
    "        queue = deque([])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j))\n",
    "                else:\n",
    "                    ocean += 1\n",
    "        if ocean == 0 or ocean == n ** 2:\n",
    "            return steps \n",
    "        steps = 0\n",
    "        while queue:\n",
    "            steps += 1\n",
    "            for _ in range(len(queue)):\n",
    "                i, j = queue.popleft()\n",
    "\n",
    "                for di, dj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                    if 0<= di < n and 0<= dj < n and grid[di][dj] == 0:\n",
    "                        queue.append((di, dj))\n",
    "                        grid[di][dj] = -1\n",
    "                        ocean -= 1\n",
    "                    if ocean == 0:\n",
    "                        return steps\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[False]*n for _ in range(m)]\n",
    "        dis = [[0]*n for _ in range(m)]\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append((i, j))\n",
    "                    vis[i][j] = True\n",
    "        if len(q) == m*n or len(q) == 0:\n",
    "            return -1\n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for dx, dy in (x+1, y), (x-1, y), (x, y+1), (x, y-1):\n",
    "                if 0 <= dx < m and 0 <= dy < n and not vis[dx][dy]:\n",
    "                    dis[dx][dy] = dis[x][y] + 1\n",
    "                    q.append((dx, dy))\n",
    "                    vis[dx][dy] = True\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dis[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        BFS：把所有陆地都入队，然后扩撒 那么最后扩散到的海洋就是最远的海洋\n",
    "        \"\"\"\n",
    "        queue = deque()\n",
    "        dirs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    queue.append((i,j))\n",
    "        if len(queue)==0 or len(queue)==n*n:#全是海洋或者陆地\n",
    "            return -1 \n",
    "        \n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            for dx,dy in dirs:\n",
    "                newX,newY = x+dx,y+dy\n",
    "                if 0<=newX<n and 0<=newY<n and grid[newX][newY]==0:\n",
    "                    grid[newX][newY] = grid[x][y]+1\n",
    "                    queue.append((newX,newY))\n",
    "        return grid[x][y]-1 # x,y一定会取值 不然会在前面就返回了\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]\n",
    "        if len(queue) == 0 or len(queue) == n ** 2: return steps\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)): \n",
    "                x, y = queue.pop(0)\n",
    "                for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:\n",
    "                        queue.append((xi, yj))\n",
    "                        grid[xi][yj] = -1\n",
    "            steps += 1\n",
    "                \n",
    "        return steps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        que = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]\n",
    "\n",
    "        if len(que) == 0 or len(que) == n*n:\n",
    "            return steps\n",
    "        \n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                x, y = que.pop(0)\n",
    "                for xi, yj in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:\n",
    "                        que.append((xi, yj))\n",
    "                        grid[xi][yj] = -1\n",
    "            steps += 1\n",
    "        return steps\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        queue = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1])\n",
    "        step = -1\n",
    "        if len(queue) == 0 or len(queue) == n ** 2:\n",
    "            return step\n",
    "        while queue:\n",
    "            step += 1\n",
    "            for _ in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n",
    "                    new_x, new_y = x + dx, y + dy\n",
    "                    if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 0:\n",
    "                        queue.append((new_x, new_y))\n",
    "                        grid[new_x][new_y] -= 1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]\n",
    "        if len(queue) == 0 or len(queue) == n ** 2: return steps\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)): \n",
    "                x, y = queue.pop(0)\n",
    "                for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:\n",
    "                        queue.append((xi, yj))\n",
    "                        grid[xi][yj] = -1\n",
    "            steps += 1\n",
    "                \n",
    "        return steps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        step = -1\n",
    "        n = len(grid)\n",
    "        queue = deque([i, j] for i in range(n) for j in range(n) if grid[i][j] == 1)\n",
    "        if len(queue) == 0 or len(queue) == n ** 2:\n",
    "            return step\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:\n",
    "                        queue.append([nx, ny])\n",
    "                        grid[nx][ny] = -1\n",
    "            step += 1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        queue = deque([(i,j) for i in range(n) for j in range(n) if grid[i][j] ==1])\n",
    "        if len(queue) == 0 or len(queue) == n ** 2:\n",
    "            return steps \n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                i, j = queue.popleft()\n",
    "                for di, dj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:\n",
    "                    if 0<= di < n and 0<= dj < n and grid[di][dj] == 0:\n",
    "                        queue.append((di, dj))\n",
    "                        grid[di][dj] = -1\n",
    "            steps += 1\n",
    "        \n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    tmp.append((i,j))\n",
    "        if len(tmp)==0 or len(tmp) == n*n:\n",
    "            return -1\n",
    "        \n",
    "        while len(tmp) > 0:\n",
    "            for i in range(len(tmp)):\n",
    "                x,y = tmp.pop(0)\n",
    "                for p,q in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0<=p<n and 0<=q<n and grid[p][q]==0:\n",
    "                        tmp.append((p,q))\n",
    "                        grid[p][q]=-1\n",
    "            steps+=1\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        result = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for w in range(n):\n",
    "                if grid[i][w] == 1:\n",
    "                    result.append((i, w))\n",
    "                else:\n",
    "                    grid[i][w] = 0   \n",
    "\n",
    "        if len(result) == 0 or len(result) == m * n:\n",
    "            return -1\n",
    "        \n",
    "        count = 0\n",
    "        while result:\n",
    "            count += 1  \n",
    "            for i in range(len(result)):\n",
    "                x, y = result.pop(0)\n",
    "                if x + 1 < m and grid[x+1][y] == 0:\n",
    "                    result.append((x+1, y))\n",
    "                    grid[x+1][y] = -1\n",
    "                if x - 1 >= 0 and grid[x-1][y] == 0:\n",
    "                    result.append((x-1, y))\n",
    "                    grid[x-1][y] = -1\n",
    "                if y + 1 < n and grid[x][y+1] == 0:\n",
    "                    result.append((x, y+1))\n",
    "                    grid[x][y+1] = -1\n",
    "                if y - 1 >= 0 and grid[x][y-1] == 0:\n",
    "                    result.append((x, y-1))\n",
    "                    grid[x][y-1] = -1\n",
    "        \n",
    "        return count - 1\n",
    "\n",
    "# 作者：风云2020\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        ocean = 0\n",
    "        #queue = deque([(i,j) for i in range(n) for j in range(n) if grid[i][j] ==1])\n",
    "        queue = deque([])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j))\n",
    "                else:\n",
    "                    ocean += 1\n",
    "        if ocean == 0 or ocean == n ** 2:\n",
    "            return steps \n",
    "        steps = 0\n",
    "        while queue:\n",
    "            steps += 1\n",
    "            for _ in range(len(queue)):\n",
    "                i, j = queue.popleft()\n",
    "                di, dj = i+1, j\n",
    "                if 0<= di < n and 0<= dj < n and grid[di][dj] == 0:\n",
    "                    queue.append((di, dj))\n",
    "                    grid[di][dj] = -1\n",
    "                    ocean -= 1\n",
    "                di, dj = i-1, j\n",
    "                if 0<= di < n and 0<= dj < n and grid[di][dj] == 0:\n",
    "                    queue.append((di, dj))\n",
    "                    grid[di][dj] = -1\n",
    "                    ocean -= 1\n",
    "                di, dj = i, j+1\n",
    "                if 0<= di < n and 0<= dj < n and grid[di][dj] == 0:\n",
    "                    queue.append((di, dj))\n",
    "                    grid[di][dj] = -1\n",
    "                    ocean -= 1\n",
    "                di, dj = i, j-1\n",
    "                if 0<= di < n and 0<= dj < n and grid[di][dj] == 0:\n",
    "                    queue.append((di, dj))\n",
    "                    grid[di][dj] = -1\n",
    "                    ocean -= 1\n",
    "\n",
    "                if ocean == 0:\n",
    "                    return steps\n",
    "            \n",
    "\n",
    "            \n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        queue=deque([])\n",
    "        dic=[[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    queue.append([i,j])\n",
    "        if len(queue)==n*n or len(queue)==0:\n",
    "            return -1\n",
    "        p=0\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for _ in range(size):\n",
    "                a,b=queue.popleft()\n",
    "                for x,y in dic:\n",
    "                    x+=a\n",
    "                    y+=b\n",
    "                    if 0<=x<n and 0<=y<n and grid[x][y]==0:\n",
    "                        queue.append([x,y])\n",
    "                        grid[x][y]=1\n",
    "            p+=1\n",
    "        return p-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "import sys\r\n",
    "class Solution:\r\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\r\n",
    "        H, W = len(grid), len(grid[0])\r\n",
    "        v = []\r\n",
    "\r\n",
    "        ans = 0\r\n",
    "        dp1 =  [[-1 for _ in range(W)] for _ in range(H)]\r\n",
    "        dp2 =  [[-1 for _ in range(W)] for _ in range(H)]\r\n",
    "        dp3 =  [[-1 for _ in range(W)] for _ in range(H)]\r\n",
    "        dp4 =  [[-1 for _ in range(W)] for _ in range(H)]\r\n",
    "        for h in range(H):\r\n",
    "            for w in range(W):\r\n",
    "                if grid[h][w] == 1:\r\n",
    "                    dp1[h][w] = 0\r\n",
    "                else:\r\n",
    "                    d = min((dp1[h-1][w] if h>0 else sys.maxsize), (dp1[h][w-1] if w>0 else sys.maxsize))\r\n",
    "                    if d < sys.maxsize:\r\n",
    "                        d += 1\r\n",
    "                    dp1[h][w] = d\r\n",
    "        for h in range(H-1, -1, -1):\r\n",
    "            for w in range(W-1, -1, -1):\r\n",
    "                if grid[h][w] == 1:\r\n",
    "                    dp2[h][w] = 0\r\n",
    "                else:\r\n",
    "                    d = min((dp2[h+1][w] if h<H-1 else sys.maxsize), (dp2[h][w+1] if w<W-1 else sys.maxsize))\r\n",
    "                    if d < sys.maxsize:\r\n",
    "                        d += 1\r\n",
    "                    dp2[h][w] = d\r\n",
    "        for h in range(H-1, -1, -1):\r\n",
    "            for w in range(W):\r\n",
    "                if grid[h][w] == 1:\r\n",
    "                    dp3[h][w] = 0\r\n",
    "                else:\r\n",
    "                    d = min((dp3[h+1][w] if h<H-1 else sys.maxsize), (dp3[h][w-1] if w>0 else sys.maxsize))\r\n",
    "                    if d < sys.maxsize:\r\n",
    "                        d += 1\r\n",
    "                    dp3[h][w] = d\r\n",
    "        for h in range(H):\r\n",
    "            for w in range(W-1, -1, -1):\r\n",
    "                if grid[h][w] == 1:\r\n",
    "                    dp4[h][w] = 0\r\n",
    "                else:\r\n",
    "                    d = min((dp4[h-1][w] if h>0 else sys.maxsize), (dp4[h][w+1] if w<W-1 else sys.maxsize))\r\n",
    "                    if d < sys.maxsize:\r\n",
    "                        d += 1\r\n",
    "                    dp4[h][w] = d\r\n",
    "        for h in range(H):\r\n",
    "            for w in range(W):\r\n",
    "                if grid[h][w] == 0:\r\n",
    "                    cur_dist = min(dp1[h][w], dp2[h][w], dp3[h][w], dp4[h][w])\r\n",
    "                    # 当全部是海洋，不存在陆地\r\n",
    "                    if cur_dist == sys.maxsize:\r\n",
    "                        return -1\r\n",
    "                    ans = max(ans, cur_dist)\r\n",
    "        # 当全部是陆地，不存在海洋\r\n",
    "        if ans == 0:\r\n",
    "            ans = -1\r\n",
    "                \r\n",
    "        return ans\r\n",
    "                \r\n",
    "        \r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        steps = -1\n",
    "        queue = collections.deque([(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1])\n",
    "        if len(queue) == 0 or len(queue) == n ** 2: return steps\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:\n",
    "                        queue.append((xi, yj))\n",
    "                        grid[xi][yj] = -1\n",
    "            steps += 1\n",
    "\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        g = [[inf]*n for _ in range(n)]\n",
    "        ans,heap = -1,[]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    g[i][j] = 0\n",
    "                    heap.append([0,i,j])\n",
    "        while heap:\n",
    "            step,r,c = heapq.heappop(heap)\n",
    "            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                next_r,next_c = r+x,c+y\n",
    "                if 0 <= next_r < n and 0 <= next_c < n and g[next_r][next_c] > step + 1:\n",
    "                    g[next_r][next_c] = step + 1\n",
    "                    heapq.heappush(heap,[step+1,next_r,next_c])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans = max(ans,g[i][j])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        ans = -1\n",
    "        n = len(grid)\n",
    "        queue = collections.deque()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i,j))\n",
    "        \n",
    "        if  len(queue) == n**2:\n",
    "            return -1\n",
    "\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            queue_copy = queue.copy()\n",
    "            queue = collections.deque()\n",
    "            for x,y in queue_copy:\n",
    "                if x + 1 < n and not grid[x + 1][y]:\n",
    "                    grid[x+1][y] = grid[x][y] + 1\n",
    "                    queue.append((x+1,y))\n",
    "                if y + 1 < n and not grid[x ][y + 1]:\n",
    "                    grid[x][y + 1] = grid[x][y] + 1\n",
    "                    queue.append((x,y+1))\n",
    "                if x - 1 >= 0 and not grid[x - 1][y]:\n",
    "                    grid[x-1][y] = grid[x][y] + 1\n",
    "                    queue.append((x-1,y))\n",
    "                if y - 1 >=0 and not grid[x ][y - 1]:\n",
    "                    grid[x][y - 1] = grid[x][y] + 1\n",
    "                    queue.append((x,y - 1))\n",
    "        return  ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        ones:List = [(x,y) for x in range(len(grid)) for y in range(len(grid)) if grid[x][y]==1]\n",
    "        dis = -1\n",
    "        if (len(ones)==len(grid)**2):\n",
    "            return -1\n",
    "        while ones:\n",
    "            dis+=1\n",
    "            temp=[]\n",
    "            for (x,y) in ones:\n",
    "                for (xi,yi) in [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]:\n",
    "                    if xi>=0 and xi<=len(grid)-1 and yi>=0 and yi<=len(grid)-1 and grid[xi][yi]==0:\n",
    "                        grid[xi][yi]=-1\n",
    "                        temp.append((xi,yi))\n",
    "            ones=temp\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import *\n",
    "from collections import defaultdict\n",
    "from  copy import *\n",
    "class Solution:\n",
    "    def func(self,i,j,f,grid,ans,m,n):\n",
    "        '''if i==4 and j==0:\n",
    "            '''\n",
    "        if i-1>=0 and f[i-1][j]==1:\n",
    "            ans[i][j] = min(ans[i][j],1+ans[i-1][j])\n",
    "        if i+1<m and f[i+1][j]==1:\n",
    "            ans[i][j] = min(ans[i][j],1+ans[i+1][j])\n",
    "        if j-1>=0 and f[i][j-1]==1:\n",
    "            ans[i][j] = min(ans[i][j],1+ans[i][j-1])\n",
    "        if j+1<n and f[i][j+1]==1:\n",
    "            ans[i][j] = min(ans[i][j],1+ans[i][j+1])\n",
    "\n",
    "\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n,= len(grid),len(grid[0])\n",
    "        f = [[0]*n for _ in range(m)]\n",
    "        ans = [[m+n]*n for _ in range(m)]\n",
    "        total = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    f[i][j]=1\n",
    "                    ans[i][j]=0\n",
    "                else:\n",
    "                    total+=1\n",
    "        if total in [0,m*n]:\n",
    "            return -1\n",
    "        # [print(i) for i in ans]\n",
    "        while total>0:\n",
    "            f_ = deepcopy(f)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if f_[i][j]==0 and grid[i][j]==0:\n",
    "                        self.func(i,j,f_,grid,ans,m,n)\n",
    "                        if ans[i][j]!=m+n:\n",
    "                            f[i][j]=1\n",
    "                            total-=1\n",
    "        maxs = ans[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                maxs = max(maxs,ans[i][j])\n",
    "        [print(i) for i in ans]\n",
    "        return maxs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        start = []\n",
    "        for i in range(rows): # 将所有起点存入 start 数组\n",
    "            for j in range(cols):\n",
    "                if grid[i][j] == 1:\n",
    "                    start.append((i, j, 0))\n",
    "        \n",
    "        if len(start) == 0 or len(start) == rows * cols: # 特判\n",
    "            return -1\n",
    "\n",
    "        queue = collections.deque(start) # 队列初始化\n",
    "        dr = [0, 1, 0, -1] # 建立方向数组\n",
    "        dc = [1, 0, -1, 0]\n",
    "        while queue:\n",
    "            i, j, dis = queue.popleft()\n",
    "            for d in range(4): # 四个方向\n",
    "                x = i + dr[d]\n",
    "                y = j + dc[d]\n",
    "                if x < 0 or y < 0 or x == rows or y == cols or grid[x][y] == 1: \n",
    "                    continue\n",
    "                queue.append((x, y, dis + 1))\n",
    "                grid[x][y] = 1 # 访问过的位置标记为 1\n",
    "                \n",
    "        return dis "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Multi-source BFS\n",
    "    time: O(n^2)\n",
    "    space: O(n^2) for <dist>, O(n^2) for <queue>,\n",
    "        totally, O(n^2).\n",
    "    \"\"\"\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        queue = [] \n",
    "\n",
    "        for x in range(n):\n",
    "            for y in range(n):\n",
    "                if grid[x][y]:\n",
    "                    queue.append((x, y))\n",
    "\n",
    "        res = -1\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        dist = grid.copy()\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            res = dist[x][y]\n",
    "            for dx, dy in directions:\n",
    "                if (\n",
    "                    0 <= x+dx < n and\n",
    "                    0 <= y+dy < n and\n",
    "                    dist[x+dx][y+dy] == 0\n",
    "                ):\n",
    "                    queue.append([x+dx, y+dy])\n",
    "                    dist[x+dx][y+dy] = dist[x][y] + 1\n",
    "        return res - 1 if res > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        ans,n = -1,len(grid)\n",
    "        g = [[inf]*n for _ in range(n)]\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    g[i][j] = 0\n",
    "                    heap.append([0,i,j])\n",
    "        while heap:\n",
    "            step,r,c = heapq.heappop(heap)\n",
    "            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                next_r,next_c = r+x,c+y\n",
    "                if 0 <= next_r < n and 0 <= next_c < n and g[next_r][next_c] > step + 1:\n",
    "                    g[next_r][next_c] = step + 1\n",
    "                    heapq.heappush(heap,[step+1,next_r,next_c])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    ans = max(ans,g[i][j])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        land=[]\n",
    "        f1=f2=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    f1=1\n",
    "                    land.append([i,j])\n",
    "                    grid[i][j]=-1\n",
    "                elif grid[i][j]==0:\n",
    "                    f2=1\n",
    "                    grid[i][j]=float(\"inf\")\n",
    "        if f1==0 or f2==0:\n",
    "            return -1\n",
    "        for i,j in land:\n",
    "            stack=collections.deque()\n",
    "            stack.append([i,j,0])\n",
    "            while stack:\n",
    "                x,y,d=stack.popleft()\n",
    "                for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                    if 0<=x1<n and 0<=y1<n and grid[x1][y1]!=-1:\n",
    "                        tmp=d+1\n",
    "                        if grid[x1][y1]>tmp:\n",
    "                            grid[x1][y1]=tmp\n",
    "                            stack.append([x1,y1,tmp])\n",
    "        mx=0 \n",
    "        for i in range(n):\n",
    "            t=max(grid[i])\n",
    "            mx=max(t,mx)\n",
    "        return mx \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        res=[[0] *m for i in range(n)]\n",
    "        steps=-1\n",
    "        ones_pos=[(i,j) for i in range(n) for j in range(m) if grid[i][j]==1]\n",
    "        q=collections.deque(ones_pos)\n",
    "        if len(q) == 0 or len(q) == n*m:\n",
    "            return steps\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                i,j=q.popleft()\n",
    "                for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    if 0<=ni<n and 0<=nj<m and grid[ni][nj] ==0:\n",
    "                        grid[ni][nj]=-1\n",
    "                        q.append((ni,nj))\n",
    "            steps+=1     \n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dx = [1, 0, -1, 0]\n",
    "    dy = [0, 1, 0, -1]\n",
    "\n",
    "    def bfs(self, i, j, visit, grid, n, m):\n",
    "        \n",
    "        q = [(i, j, 0)]\n",
    "        visit[i][j] = 1\n",
    "        while q:\n",
    "            r = q.pop()\n",
    "            x, y, dist = r\n",
    "\n",
    "            for k in range(4):\n",
    "                x = x + self.dx[k]\n",
    "                y = y + self.dy[k]\n",
    "\n",
    "                if x >= 0 and x < n and y >=0 and y < m:\n",
    "                    if visit[x][y]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        q.append((x, y, dist + 1))\n",
    "                        visit[x][y] = 1\n",
    "                    if grid[x][y] == 1:\n",
    "                        return dist +1\n",
    "        \n",
    "        return -1\n",
    "\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "\n",
    "        if n == 1 and m == 1:\n",
    "            if grid[0][0] == 0:\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        visit = [[0 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "        ans = -1\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append((i,j,0))\n",
    "                    visit[i][j] == 1\n",
    "        # print(q)\n",
    "        if not q:\n",
    "            return -1\n",
    "\n",
    "        isocean = False\n",
    "\n",
    "        def bfs( visit, q):\n",
    "            mmax = 0\n",
    "            nonlocal isocean\n",
    "\n",
    "            while q:\n",
    "                r = q.pop(0)\n",
    "                x0, y0, dist = r\n",
    "                visit[x0][y0] = 1\n",
    "                if not isocean and grid[x0][y0] == 0:\n",
    "                    isocean = True\n",
    "\n",
    "                for k in range(4):\n",
    "                    x = x0 + self.dx[k]\n",
    "                    y = y0 + self.dy[k]\n",
    "                    # print(x, y)\n",
    "                    if x >= 0 and x < n and y >=0 and y < m:\n",
    "                        if visit[x][y]:\n",
    "\n",
    "                            continue\n",
    "                        else:\n",
    "                            q.append((x, y, dist + 1))\n",
    "                            visit[x][y] = 1\n",
    "                            # print((x,y, dist+1))\n",
    "                            mmax = max(mmax, dist + 1)\n",
    "            \n",
    "            return mmax\n",
    "\n",
    "        mmax = bfs(visit, q)\n",
    "        if not isocean:\n",
    "            return -1\n",
    "        else:\n",
    "            return mmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append((i,j))\n",
    "        if len(q)==0 or len(q)==n*n:\n",
    "            return -1\n",
    "        \n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for x,y in tmp:\n",
    "                for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                    if 0<=nx<n and 0<=ny<n and grid[nx][ny]==0:\n",
    "                        grid[nx][ny] = -1\n",
    "                        q.append((nx,ny))\n",
    "            level += 1\n",
    "        return level-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        used=[[-1]*n for _ in range(m)]\n",
    "        nowlist=[]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    used[i][j]=0\n",
    "                    nowlist.append([i,j])\n",
    "        dirs=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        while len(nowlist)!=0:\n",
    "            tmplist=[]\n",
    "            for item in nowlist:\n",
    "                x=item[0]\n",
    "                y=item[1]\n",
    "                for d in dirs:\n",
    "                    nx=x+d[0]\n",
    "                    ny=y+d[1]\n",
    "                    if nx>=0 and nx<m and ny>=0 and ny<n:\n",
    "                        if grid[nx][ny]==0 and used[nx][ny]==-1:\n",
    "                            used[nx][ny]=used[x][y]+1\n",
    "                            res=used[nx][ny]\n",
    "                            tmplist.append([nx,ny])\n",
    "            nowlist=tmplist\n",
    "        if res==0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        arr = [[]]\n",
    "        move = [-1,0,1,0,-1]\n",
    "        rl,cl = len(grid[0]),len(grid)\n",
    "        for i in range(cl):\n",
    "            for j in range(rl):\n",
    "                if grid[i][j]:\n",
    "                    arr[0].append((i,j))\n",
    "        if not arr[0] or len(arr[0])==rl*cl:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        while arr[ans]:\n",
    "            t = arr[ans]\n",
    "            ans += 1\n",
    "            arr.append([])\n",
    "            for i,j in t:\n",
    "                for k in range(4):\n",
    "                    c = i + move[k]\n",
    "                    r = j + move[k+1]\n",
    "                    if 0 <= c < cl and 0 <= r < rl and not grid[c][r]:\n",
    "                        grid[c][r] = 1\n",
    "                        arr[ans].append((c,r))\n",
    "        return ans - 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        start = []\n",
    "        for i in range(rows): # 将所有起点存入 start 数组\n",
    "            for j in range(cols):\n",
    "                if grid[i][j] == 1:\n",
    "                    start.append((i, j, 0))\n",
    "        \n",
    "        if len(start) == 0 or len(start) == rows * cols: # 特判\n",
    "            return -1\n",
    "\n",
    "        queue = collections.deque(start) # 队列初始化\n",
    "        dr = [0, 1, 0, -1] # 建立方向数组\n",
    "        dc = [1, 0, -1, 0]\n",
    "        while queue:\n",
    "            i, j, dis = queue.popleft()\n",
    "            for d in range(4): # 四个方向\n",
    "                x = i + dr[d]\n",
    "                y = j + dc[d]\n",
    "                if x < 0 or y < 0 or x == rows or y == cols or grid[x][y] == 1: \n",
    "                    continue\n",
    "                queue.append((x, y, dis + 1))\n",
    "                grid[x][y] = 1 # 访问过的位置标记为 1\n",
    "                \n",
    "        return dis "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        quene = [[0,0] for _ in range(n*m)]\n",
    "        visited = [[False for _ in range(m)] for _ in range(n)]\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        seas = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    quene[r][0] = i\n",
    "                    quene[r][1] = j\n",
    "                    visited[i][j] = True\n",
    "                    r += 1\n",
    "                else:\n",
    "                    visited[i][j] = False\n",
    "                    seas += 1\n",
    "        if seas == 0 or seas == m*n:\n",
    "            return -1 \n",
    "        level = 0\n",
    "        while l < r:\n",
    "            level += 1\n",
    "            size = r - l\n",
    "            for _ in range(size):\n",
    "                x = quene[l][0]\n",
    "                y = quene[l][1]\n",
    "                l += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + move[i]\n",
    "                    ny = y + move[i+1]\n",
    "                    if nx >= 0 and nx < n and ny >= 0 and ny < m and grid[nx][ny] == 0 and not visited[nx][ny]:\n",
    "                        visited[nx][ny] = True\n",
    "                        quene[r][0] = nx\n",
    "                        quene[r][1] = ny\n",
    "                        r += 1\n",
    "        return level - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        stack = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    stack.append([i, j])\n",
    "\n",
    "        if len(stack) == m*n or not stack:\n",
    "            return -1\n",
    "\n",
    "        step = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i, j in stack:\n",
    "                for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                    if 0<=x<m and 0<=y<n and not grid[x][y]:\n",
    "                        nex.append([x, y])\n",
    "                        grid[x][y] = step\n",
    "            stack = nex\n",
    "            step += 1\n",
    "        return step-2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        is1 = []\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    is1.append((i, j))\n",
    "                    queue.append((i, j))\n",
    "        \n",
    "        last = None\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for a, b in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):\n",
    "                if 0 <= a < m and 0 <= b < m and grid[a][b] == 0:\n",
    "                    grid[a][b] = 2\n",
    "                    last = (a, b)\n",
    "                    queue.append((a, b))\n",
    "        \n",
    "        if not last: return -1\n",
    "        ans = float('inf')\n",
    "        for i, j in is1:\n",
    "            ans = min(ans, abs(last[0] - i) + abs(last[1] - j))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        n = len(grid)\n",
    "        dist = [[float('inf') for _ in range(n)] for _ in range(n)]\n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dist[i][j] = 0\n",
    "                    queue.append((i, j))\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            for i in range(4):\n",
    "                u, v = x + dx[i], y+dy[i]\n",
    "                if u < 0 or u > n-1 or v < 0 or v > n-1:\n",
    "                    continue\n",
    "                if dist[u][v] == float('inf'):\n",
    "                    dist[u][v] = dist[x][y] + 1\n",
    "                    queue.append((u, v))\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and dist[i][j] > ans:\n",
    "                    ans = dist[i][j]\n",
    "        return -1 if ans == float('inf') else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        if not grid:\n",
    "            return 0\n",
    "\n",
    "        stepList = []\n",
    "        for indexi, valuei in enumerate(grid):\n",
    "            for indexj, valuej in enumerate(valuei):\n",
    "                if valuej == 1:\n",
    "                    stepList.append([indexi, indexj])\n",
    "        leni = len(grid)\n",
    "        lenj = len(grid[0])\n",
    "\n",
    "        if len(stepList) == leni * lenj:\n",
    "            return -1\n",
    "\n",
    "        currrentStep = 0\n",
    "        while stepList:\n",
    "            nextList = []\n",
    "            for i in stepList:\n",
    "\n",
    "                indexi, indexj = i[0], i[1]\n",
    "                if indexi > 0:\n",
    "                    if grid[indexi-1][indexj] == 0:\n",
    "                        grid[indexi-1][indexj] = currrentStep + 2\n",
    "                        nextList.append([indexi-1,indexj])\n",
    "\n",
    "                if indexi < leni -1:\n",
    "                    if grid[indexi+1][indexj] == 0:\n",
    "                        grid[indexi+1][indexj] = currrentStep + 2\n",
    "                        nextList.append([indexi+1,indexj])\n",
    "                \n",
    "                if indexj > 0:\n",
    "                    if grid[indexi][indexj-1] == 0:\n",
    "                        grid[indexi][indexj-1] = currrentStep + 2\n",
    "                        nextList.append([indexi,indexj-1])\n",
    "\n",
    "                if indexj < lenj -1:\n",
    "                    if grid[indexi][indexj+1] == 0:\n",
    "                        grid[indexi][indexj+1] = currrentStep + 2\n",
    "                        nextList.append([indexi,indexj+1])\n",
    "            del stepList\n",
    "            stepList = nextList\n",
    "            currrentStep += 1\n",
    "        \n",
    "        return currrentStep -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        MAXN = 101\n",
    "        MAXM = 101\n",
    "\n",
    "        queue = [[0] * 2 for _ in range(MAXN * MAXM)]\n",
    "        l, r = 0, 0\n",
    "\n",
    "        # 0:上，1:右，2:下，3:左\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        # i来到0位置 : x + move[i], y + move[i+1] -> x - 1, y\n",
    "        # i来到1位置 : x + move[i], y + move[i+1] -> x, y + 1\n",
    "        # i来到2位置 : x + move[i], y + move[i+1] -> x + 1, y\n",
    "        # i来到3位置 : x + move[i], y + move[i+1] -> x, y - 1\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        seas = 0\n",
    "        visited = [[False] * m for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    visited[i][j] = True\n",
    "                    queue[r][0] = i\n",
    "                    queue[r][1] = j\n",
    "                    r += 1\n",
    "                else:\n",
    "                    visited[i][j] = False\n",
    "                    seas += 1\n",
    "\n",
    "        if seas == 0 or seas == n * m:\n",
    "            return -1\n",
    "\n",
    "        level = 0\n",
    "        while l < r:\n",
    "            level += 1\n",
    "            size = r - l\n",
    "\n",
    "            for k in range(size):\n",
    "                x, y = queue[l][0], queue[l][1]\n",
    "                l += 1\n",
    "\n",
    "                for i in range(4):\n",
    "                    # 上、右、下、左\n",
    "                    nx, ny = x + move[i], y + move[i + 1]\n",
    "                    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:\n",
    "                        visited[nx][ny] = True\n",
    "                        queue[r][0] = nx\n",
    "                        queue[r][1] = ny\n",
    "                        r += 1\n",
    "\n",
    "        return level - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        def dis(pos1, pos2):\n",
    "            return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])\n",
    "\n",
    "\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        maps = {}\n",
    "\n",
    "        que = collections.deque()\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    que.append((i, j))\n",
    "                    maps[i * m + j] = 0\n",
    "        res = -1\n",
    "\n",
    "        while que:\n",
    "            cx, cy = que.popleft()\n",
    "            step = maps[cx * m + cy]\n",
    "\n",
    "            for dx, dy in directions:\n",
    "\n",
    "                nx, ny = cx + dx, cy + dy\n",
    "\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m: continue\n",
    "\n",
    "                if grid[nx][ny] != 0: continue\n",
    "                grid[nx][ny] = step + 1\n",
    "                que.append((nx, ny))\n",
    "                maps[nx * m + ny] = step + 1\n",
    "                res = max(res, step + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        MAXN = 101\n",
    "        MAXM = 101\n",
    "\n",
    "        queue = [[0] * 2 for _ in range(MAXN * MAXN)]\n",
    "        l, r = 0, 0\n",
    "\n",
    "        # 0:上，1:右，2:下，3:左\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        # i来到0位置 : x + move[i], y + move[i+1] -> x - 1, y\n",
    "        # i来到1位置 : x + move[i], y + move[i+1] -> x, y + 1\n",
    "        # i来到2位置 : x + move[i], y + move[i+1] -> x + 1, y\n",
    "        # i来到3位置 : x + move[i], y + move[i+1] -> x, y - 1\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        seas = 0\n",
    "        visited = [[False] * m for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    visited[i][j] = True\n",
    "                    queue[r][0] = i\n",
    "                    queue[r][1] = j\n",
    "                    r += 1\n",
    "                else:\n",
    "                    visited[i][j] = False\n",
    "                    seas += 1\n",
    "\n",
    "        if seas == 0 or seas == n * m:\n",
    "            return -1\n",
    "\n",
    "        level = 0\n",
    "        while l < r:\n",
    "            level += 1\n",
    "            size = r - l\n",
    "\n",
    "            for k in range(size):\n",
    "                x, y = queue[l][0], queue[l][1]\n",
    "                l += 1\n",
    "\n",
    "                for i in range(4):\n",
    "                    # 上、右、下、左\n",
    "                    nx, ny = x + move[i], y + move[i + 1]\n",
    "                    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:\n",
    "                        visited[nx][ny] = True\n",
    "                        queue[r][0] = nx\n",
    "                        queue[r][1] = ny\n",
    "                        r += 1\n",
    "\n",
    "        return level - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        stack = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    stack.append([i, j])\n",
    "\n",
    "        if len(stack) == m*n or not stack:\n",
    "            return -1\n",
    "\n",
    "        step = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i, j in stack:\n",
    "                for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                    if 0<=x<m and 0<=y<n and not grid[x][y]:\n",
    "                        nex.append([x, y])\n",
    "                        grid[x][y] = step\n",
    "            stack = nex\n",
    "            step += 1\n",
    "        return step-2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        g = []\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    g.append([i,j])\n",
    "        if len(g) == n*n or len(g) == 0:\n",
    "            return -1\n",
    "        q = [g]\n",
    "\n",
    "        count = 0\n",
    "        while q:\n",
    "            # la = grid\n",
    "            grounds = q.pop(0)\n",
    "            new = []\n",
    "            count += 1\n",
    "            for i,j in grounds:\n",
    "                for h, w in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                    new_i = i + h\n",
    "                    new_j = j + w\n",
    "                    if 0<=new_i<n and 0<=new_j<n and grid[new_i][new_j] == 0:\n",
    "                        new.append([new_i,new_j])\n",
    "                        grid[new_i][new_j] = 2\n",
    "            if new:\n",
    "                q.append(new)\n",
    "        # print(la)\n",
    "        return count-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        def dis(pos1, pos2):\n",
    "            return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])\n",
    "\n",
    "\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        maps = {}\n",
    "\n",
    "        que = collections.deque()\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    que.append((i, j))\n",
    "                    maps[i * m + j] = 0\n",
    "        res = -1\n",
    "\n",
    "        while que:\n",
    "            cx, cy = que.popleft()\n",
    "            step = maps[cx * m + cy]\n",
    "\n",
    "            for dx, dy in directions:\n",
    "\n",
    "                nx, ny = cx + dx, cy + dy\n",
    "\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m: continue\n",
    "\n",
    "                if grid[nx][ny] != 0: continue\n",
    "                grid[nx][ny] = step + 1\n",
    "                que.append((nx, ny))\n",
    "                maps[nx * m + ny] = step + 1\n",
    "                res = max(res, step + 1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        quene = [[0,0] for _ in range(n*m)]\n",
    "        visited = [[False for _ in range(m)] for _ in range(n)]\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        seas = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    quene[r][0] = i\n",
    "                    quene[r][1] = j\n",
    "                    visited[i][j] = True\n",
    "                    r += 1\n",
    "                else:\n",
    "                    visited[i][j] = False\n",
    "                    seas += 1\n",
    "        if seas == 0 or seas == m*n:\n",
    "            return -1 \n",
    "        level = 0\n",
    "        while l < r:\n",
    "            level += 1\n",
    "            size = r - l\n",
    "            for _ in range(size):\n",
    "                x = quene[l][0]\n",
    "                y = quene[l][1]\n",
    "                l += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + move[i]\n",
    "                    ny = y + move[i+1]\n",
    "                    if nx >= 0 and nx < n and ny >= 0 and ny < m and grid[nx][ny] == 0 and not visited[nx][ny]:\n",
    "                        visited[nx][ny] = True\n",
    "                        quene[r][0] = nx\n",
    "                        quene[r][1] = ny\n",
    "                        r += 1\n",
    "        return level - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        ans, n = -1, len(grid)\n",
    "        q, dic = deque((i, j) for i in range(n) for j in range(n) if grid[i][j] == 1), defaultdict(int)\n",
    "        while q:\n",
    "            temp = q.popleft()\n",
    "            x, y = temp[0], temp[1]\n",
    "            for dir in [(1, 0), (-1, 0), (0, -1), (0, 1)]:\n",
    "                nx, ny = x + dir[0], y + dir[1]\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= n or grid[nx][ny] != 0:continue\n",
    "                step = dic[x * n + y]\n",
    "                grid[nx][ny] = step + 1\n",
    "                dic[nx * n + ny] = step + 1\n",
    "                q.append([nx, ny])\n",
    "                ans = max(ans, step + 1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\r\n",
    "        self.grid = grid\r\n",
    "        self.land = []\r\n",
    "        self.land_num = 0\r\n",
    "        distance = 0\r\n",
    "        n = len(grid)\r\n",
    "        for row in range(n):\r\n",
    "            for col in range(n):\r\n",
    "                if grid[row][col] == 1:\r\n",
    "                    self.land.append([row, col])\r\n",
    "                    self.land_num += 1\r\n",
    "\r\n",
    "        if self.land_num == 0 or self.land_num == n * n:\r\n",
    "            return -1\r\n",
    "\r\n",
    "        four_direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]\r\n",
    "        while self.land_num != n * n:\r\n",
    "            cur_num = len(self.land)\r\n",
    "            for i in range(cur_num):\r\n",
    "                land = self.land[i]\r\n",
    "                # print(land)\r\n",
    "                for direction in four_direction:\r\n",
    "                    cur_land = [land[0] + direction[0], land[1] + direction[1]]\r\n",
    "                    # print(cur_land)\r\n",
    "                    if self.is_in_grid(cur_land, n) and not self.is_land(cur_land):\r\n",
    "                        self.grid[cur_land[0]][cur_land[1]] = 1\r\n",
    "                        self.land.append(cur_land)\r\n",
    "                        self.land_num += 1\r\n",
    "            self.land = self.land[cur_num:]\r\n",
    "\r\n",
    "            distance += 1\r\n",
    "        return distance\r\n",
    "\r\n",
    "    def is_land(self, land):\r\n",
    "        return self.grid[land[0]][land[1]] == 1\r\n",
    "\r\n",
    "    def is_in_grid(self, land, n):\r\n",
    "        return 0 <= land[0] < n and 0 <= land[1] < n\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        lands = []\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    lands.append([i, j])\n",
    "        if not lands or len(lands) == n*n:\n",
    "            return -1\n",
    "        \n",
    "        curpoint = []\n",
    "        queue = lands[:]\n",
    "        curqueue = []\n",
    "        while queue:\n",
    "            curpoint = queue.pop(0)\n",
    "            x, y = curpoint\n",
    "            if x+1 < n and not grid[x+1][y]:\n",
    "                curqueue.append([x+1, y])\n",
    "                grid[x+1][y] = 1\n",
    "            if 0 <= x-1 and not grid[x-1][y]:\n",
    "                curqueue.append([x-1, y])\n",
    "                grid[x-1][y] = 1\n",
    "            if 0 <= y-1 and not grid[x][y-1]:\n",
    "                curqueue.append([x, y-1])\n",
    "                grid[x][y-1] = 1\n",
    "            if y+1 < n and not grid[x][y+1]:\n",
    "                curqueue.append([x, y+1])\n",
    "                grid[x][y+1] = 1\n",
    "            if not queue:\n",
    "                queue = curqueue[:]\n",
    "                curqueue = []\n",
    "        \n",
    "        ans = 2*n\n",
    "        for point in lands:\n",
    "            ans = min(abs(point[0] - curpoint[0]) + abs(point[1] - curpoint[1]), ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        level = set()\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    level.add((i, j))\n",
    "                    visited.add((i, j))\n",
    "\n",
    "        if not level or len(level) == n * n: return -1\n",
    "\n",
    "        step = 0\n",
    "        while level:\n",
    "            new_level = set()\n",
    "            step += 1\n",
    "            for x, y in level:\n",
    "                for ox, oy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    new_x, new_y = x + ox, y + oy\n",
    "                    if 0 <= new_x < n and 0 <= new_y < n and (new_x, new_y) not in visited:\n",
    "                        visited.add((new_x, new_y))\n",
    "                        new_level.add((new_x, new_y))\n",
    "            level = new_level\n",
    "\n",
    "        return step - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        res = -1\n",
    "        direct = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        dic = {}\n",
    "        q = deque()\n",
    "        vist = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    dic[i*n+j] = 0\n",
    "                    q.append((i,j))\n",
    "                    vist.add((i,j))\n",
    "        i = 0\n",
    "        while q:\n",
    "            xn,yn=q.popleft()\n",
    "            step = dic[xn*n+yn]\n",
    "            for d in direct:\n",
    "                xi = xn+d[0]\n",
    "                yi = yn+d[1]\n",
    "                if xi<0 or yi<0 or xi>=n or yi>=n:\n",
    "                    continue\n",
    "                if (xi,yi) in vist:\n",
    "                    continue\n",
    "                q.append((xi,yi))\n",
    "                vist.add((xi,yi))\n",
    "                dic[xi*n+yi] = step + 1\n",
    "                res = max(res,step+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=deque()\n",
    "        hashmap=collections.defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    q.append((i,j))\n",
    "                    hashmap[(i,j)]=0\n",
    "        ans=-inf\n",
    "        while q:\n",
    "            i,j=q.popleft()\n",
    "            for di,dj in (-1,0),(0,1),(0,-1),(1,0):\n",
    "                new_i=i+di\n",
    "                new_j=j+dj\n",
    "                if 0<=new_i<m and 0<=new_j<n and (new_i,new_j) not in hashmap and grid[new_i][new_j]==0:\n",
    "                    hashmap[(new_i,new_j)]=hashmap[(i,j)]+1\n",
    "                    q.append((new_i,new_j))\n",
    "                    ans=max(ans,hashmap[(new_i,new_j)])\n",
    "\n",
    "        return ans if ans!=-inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 1. 定义队列和访问位置\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "\n",
    "        # 2. 初始化队列和访问位置\n",
    "        dist = 0\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    que.appendleft((i,j))\n",
    "                    visited[(i, j)] = True\n",
    "        \n",
    "        # 3. 判断边界条件\n",
    "        if not que or len(que) == n * n:\n",
    "            return -1\n",
    "        \n",
    "        # 3. 循环队列里的点\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                x, y = que.pop()\n",
    "                for pos_w, pos_h in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                    x_new = x + pos_w\n",
    "                    y_new = y + pos_h\n",
    "\n",
    "                    # 4. 判断路径是否正确\n",
    "                    if 0 <= x_new < n and 0 <= y_new < n and grid[x_new][y_new] == 0 and not visited.get((x_new, y_new)):\n",
    "                        que.appendleft((x_new, y_new))\n",
    "                        visited[(x_new, y_new)] = True\n",
    "                \n",
    "            dist += 1\n",
    "        \n",
    "        return dist-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        ans = -1\n",
    "\n",
    "        queue = deque()\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j, 0))\n",
    "        \n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        dist_map = {}\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            cur_x = cur[0]\n",
    "            cur_y = cur[1]\n",
    "            cur_d = cur[2]\n",
    "\n",
    "            for d in dirs:\n",
    "                nx = cur_x + d[0]\n",
    "                ny = cur_y + d[1]\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 1:\n",
    "                    if (nx, ny) not in dist_map:\n",
    "                        dist_map[(nx, ny)] = cur_d + 1\n",
    "                        queue.append((nx, ny, cur_d + 1))\n",
    "                        ans = max(ans, cur_d + 1)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, layer_queue, visited_mark):\n",
    "        n = len(self.grid)\n",
    "        this_layer_mark = set(layer_queue)\n",
    "        for _ in range(len(layer_queue)):  # empty queue for **this round**.\n",
    "            x, y = layer_queue.popleft()\n",
    "            visited_mark.add((x, y))\n",
    "            for x_move, y_move in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                new_x = x + x_move\n",
    "                new_y = y + y_move\n",
    "                if 0 <= new_x < n and 0 <= new_y < n \\\n",
    "                        and (new_x, new_y) not in visited_mark \\\n",
    "                        and (new_x, new_y) not in this_layer_mark:\n",
    "                    layer_queue.append((new_x, new_y))\n",
    "\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        self.grid = grid\n",
    "        n = len(grid)\n",
    "        max_res = -1\n",
    "        layer_queue = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j]==1])\n",
    "        visited_mark = set()\n",
    "        land_num = len(layer_queue)\n",
    "        ocean_num = n ** 2 - land_num\n",
    "        if land_num == 0 or ocean_num == 0:\n",
    "            return max_res\n",
    "        while layer_queue:\n",
    "            # print(layer_queue)\n",
    "            # print(f\"visited_mark{visited_mark}\")\n",
    "            self.bfs(layer_queue, visited_mark)\n",
    "            max_res += 1\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import heapq\n",
    "import math\n",
    "from operator import itemgetter\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid) -> int:\n",
    "        # land_node={}\n",
    "        queue = []\n",
    "        distance={}\n",
    "        # ocean_nodes = set()\n",
    "        #将所有陆地压入源点集，作为以S为起点的第二层\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, col in enumerate(row):\n",
    "                if col == 1:\n",
    "                    # land_node[(i, j)]=0\n",
    "                    # distance[(i, j)] = 0\n",
    "                    heapq.heappush(queue, (0, (i,j)))      #每一个陆地点到超级点S的距离都为0\n",
    "                else:\n",
    "                    distance[(i,j)] = math.inf    #每一个海洋点到超级点S的距离都初始化为无穷大\n",
    "                    # ocean_nodes.add((i,j))\n",
    "        seen = set()\n",
    "\n",
    "        #没有海洋或者没有陆地\n",
    "        if (not queue.__len__()) or (not distance.__len__()):\n",
    "            return -1\n",
    "\n",
    "        while queue.__len__():\n",
    "            dist , node = heapq.heappop(queue)\n",
    "            if node and node not in seen:\n",
    "                seen.add(node)\n",
    "                #分别访问上下左右四个点作为当前点的下一层：\n",
    "                r,c = node\n",
    "\n",
    "                # ##方法一： 节省时间，代码冗余\n",
    "                if r-1>=0 and grid[r-1][c] == 0:\n",
    "                    ocean = (r-1,c)  #up\n",
    "                    dist_ = dist + abs(node[0] - ocean[0]) + abs(node[1] - ocean[1])\n",
    "                    if distance[ocean] > dist_:\n",
    "                        distance[ocean] = dist_\n",
    "                        heapq.heappush(queue, (dist_, ocean))\n",
    "                if r + 1 <grid.__len__() and grid[r + 1][c] == 0:\n",
    "                    ocean = (r + 1, c)   #down\n",
    "                    dist_ = dist + abs(node[0] - ocean[0]) + abs(node[1] - ocean[1])\n",
    "                    if distance[ocean] > dist_:\n",
    "                        distance[ocean] = dist_\n",
    "                        heapq.heappush(queue, (dist_, ocean))\n",
    "                if c - 1 >=0 and grid[r][c-1] == 0:\n",
    "                    ocean = (r, c-1)    #left\n",
    "                    dist_ = dist + abs(node[0] - ocean[0]) + abs(node[1] - ocean[1])\n",
    "                    if distance[ocean] > dist_:\n",
    "                        distance[ocean] = dist_\n",
    "                        heapq.heappush(queue, (dist_, ocean))\n",
    "                if c + 1 < grid[0].__len__() and grid[r][c + 1] == 0:\n",
    "                    ocean = (r, c + 1)  #right\n",
    "                    dist_ = dist + abs(node[0] - ocean[0]) + abs(node[1] - ocean[1])\n",
    "                    if distance[ocean] > dist_:\n",
    "                        distance[ocean] = dist_\n",
    "                        heapq.heappush(queue, (dist_, ocean))\n",
    "\n",
    "\n",
    "                #方法二 浪费时间 代码简洁\n",
    "                \"\"\"\n",
    "                directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "                for dx, dy in directions:\n",
    "                    ocean = (r + dx, c + dy)\n",
    "                    is_valid = r + dx >= 0 and c+dy >=0 and c+dy < grid[0].__len__() and  r + dx< grid.__len__()\n",
    "                    # row_valid = ocean[0] >= 0 and ocean[0] < grid.__len__()\n",
    "                    # col_valid = ocean[1] >= 0 and ocean[1] < grid[0].__len__()\n",
    "\n",
    "                    if is_valid and grid[ocean[0]][ocean[1]] == 0:\n",
    "                        dist_ = dist + abs(dx) + abs(dy)\n",
    "                        if distance[ocean] > dist_:\n",
    "                            distance[ocean] = dist_\n",
    "                            heapq.heappush(queue, (dist_, ocean))\n",
    "                            \"\"\"\n",
    "        a= sorted(distance.items(), key= itemgetter(1),reverse=True)\n",
    "        return a[0][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        def dfs(r,c):\n",
    "            grid[r][c]=-1\n",
    "            for nr,nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):\n",
    "                if 0<=nr<n and 0<=nc<n:\n",
    "                    if grid[nr][nc]==0:\n",
    "                        q.append((r,c))\n",
    "                    elif grid[nr][nc]==1:\n",
    "                        dfs(nr,nc)\n",
    "            \n",
    "        res,q=0,[]\n",
    "        for r,c in product(range(n),repeat=2):\n",
    "            if grid[r][c]==1:\n",
    "                dfs(r,c)\n",
    "        if not q:return -1\n",
    "        while len(q):\n",
    "            q_=[]\n",
    "            res+=1\n",
    "            for r,c in q:\n",
    "                for nr,nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):\n",
    "                    if 0<=nr<n and 0<=nc<n:\n",
    "                        if grid[nr][nc]==0:\n",
    "                            grid[nr][nc]=res\n",
    "                            q_.append((nr,nc))\n",
    "            q=q_\n",
    "            \n",
    "        return res-1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        direction_i = [-1, 1, 0, 0]\n",
    "        direction_j = [0, 0, -1, 1]\n",
    "        queue = deque()\n",
    "        visited = set()\n",
    "        max_distance = 0  \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    queue.append((i, j, 0))\n",
    "        if len(queue) in [0, len(grid) * len(grid[0])]:\n",
    "            return -1\n",
    "        while queue:\n",
    "            i, j, distance = queue.popleft()\n",
    "            if (i, j) in visited: continue\n",
    "            max_distance = max(max_distance, distance)\n",
    "            visited.add((i, j))\n",
    "            for k in range(4):\n",
    "                temp_i = i + direction_i[k]\n",
    "                temp_j = j + direction_j[k]\n",
    "                if temp_i < 0 or temp_i >= len(grid) or temp_j < 0 or temp_j >= len(grid[0]):\n",
    "                    continue\n",
    "                queue.append((temp_i, temp_j, distance + 1))      \n",
    "        return max_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        que = deque()\n",
    "        n = len(grid)\n",
    "        step = -1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    que.append((i,j))\n",
    "        if len(que) == 0 or len(que) == n*n:\n",
    "            return step\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                x, y = que.popleft()\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] != -1:\n",
    "                    grid[x][y] = -1\n",
    "                    que.append((x+1, y))\n",
    "                    que.append((x, y+1))\n",
    "                    que.append((x-1, y))\n",
    "                    que.append((x, y-1))\n",
    "            step += 1\n",
    "        return step-1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            for nx, ny in ((x+1, y), (x-1, y), (x, y-1), (x, y+1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    if grid[nx][ny] == 1:\n",
    "                        dfs(nx, ny)\n",
    "                    elif grid[nx][ny] == 0:\n",
    "                        grid[nx][ny] = 2\n",
    "                        queue.append((nx, ny))\n",
    "\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j)\n",
    "        if not queue:\n",
    "            return -1\n",
    "        dist = 1\n",
    "        while queue:\n",
    "            dist += 1\n",
    "            tmp = []\n",
    "            for x, y in queue:\n",
    "                for nx, ny in ((x+1, y), (x-1, y), (x, y-1), (x, y+1)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:\n",
    "                        grid[nx][ny] = 2\n",
    "                        tmp.append((nx, ny))\n",
    "            queue = tmp\n",
    "        return dist - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"找出海洋单元格(0)离它最近的陆地单元格(1)最远的距离\"\"\"\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        dq = collections.deque()\n",
    "        # 1.找出所有的陆地单元格(1),并加入队列\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j] == 1:\n",
    "                    dq.append((i, j))\n",
    "\n",
    "        # 2.如果网格上只有陆地或者海洋，返回 -1。\n",
    "        if len(dq) == rows * cols or not dq:\n",
    "            return -1\n",
    "\n",
    "        # 3.遍历所有陆地单元格，并将4个方向还未访问的海洋单元格加入dq\n",
    "        offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        visited = set()\n",
    "\n",
    "        def inArea(x, y):\n",
    "            return 0 <= x < rows and 0 <= y < cols\n",
    "\n",
    "        # 4.bfs层序遍历dq, 每遍历一层，最远距离+1\n",
    "        maxDist = -1  # 因为第一层都是陆地，后面加入的才是海洋，所以初始值为-1\n",
    "        while dq:\n",
    "            size = len(dq)\n",
    "            for _ in range(size):\n",
    "                x, y = dq.popleft()\n",
    "                for ox, oy in offsets:\n",
    "                    newX, newY = x + ox, y + oy\n",
    "                    if inArea(newX, newY) and grid[newX][newY] == 0 and (newX, newY) not in visited:\n",
    "                        visited.add((newX, newY))\n",
    "                        dq.append((newX, newY))\n",
    "            maxDist += 1\n",
    "        return maxDist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        def bfs(layer_queue, visited_mark):\n",
    "            this_layer_mark = set(layer_queue)\n",
    "            for _ in range(len(layer_queue)):  # empty queue for **this round**.\n",
    "                x, y = layer_queue.popleft()\n",
    "                visited_mark.add((x, y))\n",
    "                for x_move, y_move in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                    new_x = x + x_move\n",
    "                    new_y = y + y_move\n",
    "                    if 0 <= new_x < n and 0 <= new_y < n \\\n",
    "                            and (new_x, new_y) not in visited_mark \\\n",
    "                            and (new_x, new_y) not in this_layer_mark:\n",
    "                        layer_queue.append((new_x, new_y))\n",
    "        n = len(grid)\n",
    "        max_res = -1\n",
    "        layer_queue = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1])\n",
    "        visited_mark = set()\n",
    "        land_num = len(layer_queue)\n",
    "        ocean_num = n ** 2 - land_num\n",
    "        if land_num == 0 or ocean_num == 0:\n",
    "            return max_res\n",
    "        while layer_queue:\n",
    "            # print(layer_queue)\n",
    "            # print(f\"visited_mark{visited_mark}\")\n",
    "            bfs(layer_queue, visited_mark)\n",
    "            max_res += 1\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        #题目中测试用例 陆地1的数量远大于海洋0的数量，如果找把海洋入队的话，会超时\n",
    "        from collections import deque\n",
    "        rows, cols = len(grid), len(grid[0]) \n",
    "        queue = deque()\n",
    "        visited = set() \n",
    "        for i in range(rows): \n",
    "            for j in range(cols): \n",
    "                if grid[i][j] == 1: \n",
    "                    queue.append((i, j)) \n",
    "                    visited.add((i, j)) \n",
    "        # 针对全是海洋（没有陆地1，queue为空），全是陆地 两种特殊情况单独返回 \n",
    "        if not queue or len(queue) == rows*cols: \n",
    "            return -1\n",
    "\n",
    "        dir = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "        # 初始化每层BFS距离和总的最大距离\n",
    "        step = 0\n",
    "        max_step = float('-inf')\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                curx, cury = queue.popleft()\n",
    "                # 第一层BFS遍历全是陆地1，不会执行，往下一层BFS全是海洋，即找到一个海洋元素，可以对比当前海洋-陆地距离和最大距离的最大值\n",
    "                if grid[curx][cury] == 0:\n",
    "                    max_step = max(max_step, step)\n",
    "                for i, j in dir:\n",
    "                    temx, temy = curx + i, cury + j\n",
    "                    # 对于已经BFS搜索过的陆地1、海洋0以及超出范围的情况，不做处理，继续下一个for循环\n",
    "              \n",
    "                    if  0 <= temx <rows and 0 <= temy < cols and (temx, temy) not in visited:\n",
    "                        queue.append((temx, temy))\n",
    "                        visited.add((temx, temy))\n",
    "            step += 1\n",
    "        \n",
    "        return max_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append([i,j,0])\n",
    "        \n",
    "        if len(q) == 0 or len(q) == row * col:\n",
    "            return -1\n",
    "        \n",
    "        dire = [[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        s = set()\n",
    "        while q:\n",
    "            x,y,dis = q.popleft()\n",
    "            for dx,dy in dire:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if not 0 <= nx < row or not 0 <= ny < col or grid[nx][ny] == 1 or (nx,ny) in s:\n",
    "                    continue\n",
    "                q.append([nx,ny,dis + 1])\n",
    "                s.add((nx,ny))\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        land = deque()\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    land.append((i,j,0))\n",
    "                    vis.add((i,j))\n",
    "        if len(land) == 0 or len(land) == n*n:\n",
    "            return -1\n",
    "        while len(vis) < n*n:\n",
    "            x,y,dis = land.popleft()\n",
    "            for xx,yy in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                if 0<=xx<n and 0<=yy<n and (xx,yy) not in vis:\n",
    "                    land.append((xx,yy,dis+1))\n",
    "                    vis.add((xx,yy))\n",
    "        return land[-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = 2\n",
    "            for nx, ny in ((x+1, y), (x-1, y), (x, y-1), (x, y+1)):\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    if grid[nx][ny] == 1:\n",
    "                        dfs(nx, ny)\n",
    "                    elif grid[nx][ny] == 0:\n",
    "                        grid[nx][ny] = 2\n",
    "                        queue.append((nx, ny))\n",
    "\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j)\n",
    "        if not queue:\n",
    "            return -1\n",
    "        dist = 1\n",
    "        while queue:\n",
    "            dist += 1\n",
    "            tmp = []\n",
    "            for x, y in queue:\n",
    "                for nx, ny in ((x+1, y), (x-1, y), (x, y-1), (x, y+1)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:\n",
    "                        grid[nx][ny] = 2\n",
    "                        tmp.append((nx, ny))\n",
    "            queue = tmp\n",
    "        return dist - 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
